package com.dalonedrau.graph;

/**
 * 
 */

import java.util.ArrayList;
import java.util.Collections;

import com.module.hq.graph.HQGraphSearchDijkstra;

/**
 * @author Donald
 */
public class DijkstraSearchImpl implements DijkstraSearch {
	/** the singleton instance of {@link DijkstraSearchImpl}. */
	private static DijkstraSearchImpl	instance;
	/**
	 * Gets the singleton instance of {@link DijkstraSearchImpl}.
	 * @return {@link DijkstraSearchImpl}
	 */
	public static DijkstraSearchImpl getInstance() {
		if (DijkstraSearchImpl.instance == null) {
			DijkstraSearchImpl.instance = new DijkstraSearchImpl();
		}
		return DijkstraSearchImpl.instance;
	}
	/** the node comparator. */
	private DijkstraComparator	comparator;
	/**
	 * this is indexed into by node index and holds the total cost of the best
	 * path found so far to the given node. For example, costToThisNode[5] will
	 * hold the total cost of all the edges that comprise the best path to node
	 * 5 found so far in the search (if node 5 is present and has been visited
	 * of course).
	 */
	private float[]				costToThisNode;
	/** the graph being searched. */
	private Graph				graph;
	/** the list of predecessor nodes. */
	private int[]				listOfPredecessors;
	/** the number of settled nodes. */
	private int					numSettled;
	/** the list of settled nodes, by index. */
	private int[]				settled;
	/** the source node from where the search originates. */
	private int					source;
	/** the list of unsettled nodes, by index. */
	private ArrayList<Integer>	unsettled;
	/** Hidden constructor. */
	private DijkstraSearchImpl() { }
	/**
	 * Adds a node index to the list of settled nodes.
	 * @param val the node index
	 */
	private void addToSettled(final int val) {
		if (numSettled + 1 >= settled.length) {
			int[] dest = new int[settled.length + 1];
			System.arraycopy(settled, 0, dest, 0, settled.length);
			settled = dest;
			dest = null;
		}
		settled[numSettled] = val;
		numSettled++;
	}
	/**
	 * Adds a node to the list of unsettled nodes.
	 * @param val the node id
	 */
	private void addToUnsettled(final int val) {
		unsettled.add(val);
		Collections.sort(unsettled, comparator);
	}
	/**
	 * {@inheritDoc}
	 */
	public float[] getDistances() {
		return costToThisNode;
	}
	private float getDistanceTo(final int val) {
		float cost = Float.POSITIVE_INFINITY;
		if (costToThisNode[val] > -1) {
			cost = costToThisNode[val];
		}
		return cost;
	}
	/**
	 * {@inheritDoc}
	 */
	public int getNumPredecessors() {
		return listOfPredecessors.length;
	}
	/**
	 * {@inheritDoc}
	 */
	public int[] getPathToTarget(final int target) {
		int[] path = new int[] { target };
		int lastNode = DijkstraSearchImpl.getInstance().getPredecessor(target);
		while (lastNode != -1) {
			int[] dest = new int[path.length + 1];
			System.arraycopy(path, 0, dest, 0, path.length);
			dest[path.length] = lastNode;
			path = dest;
			dest = null;
			lastNode = 
				DijkstraSearchImpl.getInstance().getPredecessor(lastNode);
		}
		// reverse the path
		int[] dest = new int[path.length];
		int m = path.length - 1;
		for (int i = 0; i <= m; i++) {
			dest[m - i] = path[i];
		}
		path = dest;
		dest = null;
		return path;
	}
	private int getPredecessor(final int index) {
		return listOfPredecessors[index];
	}
	/**
	 * Pops a value off the list of settled nodes.
	 * @return <code>int</code>
	 */
	private int popOffSettled() {
		int val = settled[0];
		for (int i = 1; i < settled.length; i++) {
			settled[i - 1] = settled[i];
		}
		settled[settled.length - 1] = -1;
		numSettled--;
		return val;
	}
	/**
	 * {@inheritDoc}
	 */
	public void search(final int src) throws Exception {
		if (graph == null) {
			throw new Exception("No Graph was set.");
		}
		source = src;
		comparator = new DijkstraComparator(this);
		// add source to list of unsettled vertices and immediately sort
		addToUnsettled(source);
		costToThisNode[source] = 0;
		// while the list of unsettled vertices still has nodes
		while (!unsettled.isEmpty()) {
			// get the node with the current shortest distance
			int nextClosestNode = unsettled.remove(0);
			// add next closest node to list of settled vertices
			addToSettled(nextClosestNode);
			// settled.add(nextClosestNode);
			// relax the neighbors of next closest node. For each edge connected
			// to the next closest node
			GraphEdge[] edges = graph.getEdgesFromNode(nextClosestNode);
			for (int i = 0; i < edges.length; i++) {
				int v = edges[i].getTo();
				WeightedGraphEdge edge = (WeightedGraphEdge) edges[i];
				if (!settledContains(v)) {
					float distToV = getDistanceTo(v);
					float distToU = getDistanceTo(nextClosestNode);
					if (distToV > distToU + edge.getCost()) {
						costToThisNode[v] = (float) (distToU + edge.getCost());
						listOfPredecessors[v] = nextClosestNode;
						addToUnsettled(v);
					}
				}
			}
		}
	}
	/**
	 * {@inheritDoc}
	 */
	public void setGraph(final Graph g) {
		graph = g;
		source = -1;
		if (costToThisNode == null) {
			costToThisNode = new float[graph.getNumberOfNodes()];
		} else {
			if (costToThisNode.length < graph.getNumberOfNodes()) {
				float[] dest = new float[graph.getNumberOfNodes()];
				System.arraycopy(
						costToThisNode, 0, dest, 0, costToThisNode.length);
				costToThisNode = dest;
				dest = null;
			}
		}
		for (int i = 0; i < costToThisNode.length; i++) {
			costToThisNode[i] = -1;
		}
		settled = new int[graph.getNumberOfNodes()];
		unsettled = new ArrayList<Integer>(graph.getNumberOfNodes());
		listOfPredecessors = new int[graph.getNumberOfNodes()];
		for (int i = 0; i < listOfPredecessors.length; i++) {
			listOfPredecessors[i] = -1;
		}
	}
	/**
	 * Determines if the settled array contains a specific index.
	 * @param val the index
	 * @return true if the settled array contains a specific index; false
	 *         otherwise
	 */
	private boolean settledContains(final int val) {
		boolean found = false;
		for (int i = 1; i < settled.length; i++) {
			if (settled[i] == val) {
				found = true;
				break;
			}
		}
		return found;
	}
}
